package com.gorkr.dp;

/**
 * @author gorkr
 * @date 2022/06/16 09:03
 **/
public class M712MinimumAsciiDeleteSumForTwoStrings {

    public int minimumDeleteSum(String s1, String s2) {

        // dp定义 dp[i][j] = s1[i...]和s2[j...]所需删除最小和
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        // basecase
        for (int i = s1.length() - 1; i >= 0; i--) {
            dp[i][s2.length()] = dp[i+1][s2.length()] + s1.codePointAt(i);
        }
        for (int j = s2.length() - 1; j >= 0; j--) {
            dp[s1.length()][j] = dp[s1.length()][j+1] + s2.codePointAt(j);
        }

        for (int i = s1.length()-1; i >=0; i--) {
            for (int j = s2.length()-1; j >=0; j--) {
                if(s1.charAt(i)==s2.charAt(j)){
                    dp[i][j] = dp[i+1][j+1];
                }else {
                    dp[i][j] = Math.min(dp[i+1][j]+s1.codePointAt(i),dp[i][j+1]+s2.codePointAt(j));
                    dp[i][j] = Math.min(dp[i][j],dp[i+1][j+1]+s1.codePointAt(i)+s2.codePointAt(j));
                }

            }

        }
        return dp[0][0];
    }

}
    